package structure;

import java.util.Arrays;

public class MyArrayList {
    private static final int DEFAULT_CAPACITY = 10;
    // 顺序表, 暂时使用int[] 类型
    int[] elem;

    // 有效数据个数
    int usedSize;

    public MyArrayList() {
        this.elem = new int[DEFAULT_CAPACITY];
    }

    // 判定顺序表是否为空
    public boolean isEmpty() {
        return usedSize == 0;
    }

    // 判定顺序表是否已满
    public boolean isFull() {
        return usedSize == elem.length;
    }

    // 插入元素
    public void add(int data) {
        if (isFull()) {
            grow();
        }

        elem[usedSize++] = data;
    }

    private void grow() {
        elem = Arrays.copyOf(elem, elem.length * 2);
    }

    // 在指定位置插入元素
    public void add(int data, int index) {
        if (index < 0 || index > usedSize) {
            return;
        }
        if (isFull()) {
            grow();
        }

        int i = usedSize - 1;
        while (i >= index) {
            elem[i+1] = elem[i];
            i--;
        }
        elem[index] = data;
        usedSize++;
    }

    // 查找某个元素, 返回其所在的下标
    public int indexOf(int data) {
        for (int i = 0; i < usedSize; i++) {
            if (elem[i] == data) {
                return i;
            }
        }
        // 找不到则返回-1
        return -1;
    }

    // 判断是否存在某个元素
    public boolean contains(int data) {
        // 不为-1 返回true, 说明找到该元素
        // 为-1 返回 false, 说明数组中没有该元素
        return indexOf(data) != -1;
    }

    // 通过下标查找元素并返回
    public int get(int index) {
        if (index < 0 || index >= usedSize) {
            throw new IndexOutOfBoundsException("下标异常");
        }
        return elem[index];
    }

    // 删除某个元素
    public boolean remove(int data) {
        int i = indexOf(data);
        if (i >= 0) {
            for (; i < usedSize - 1; i++) {
                elem[i+1] = elem[i];
            }
            usedSize--;
            return true;
        }
        return false;
    }

    // 移除所有值为data的元素
    public boolean removeAll(int data) {
        int i = indexOf(data);
        boolean modified = false;
        while (i >= 0) {
            for (; i < usedSize - 1; i++) {
                elem[i+1] = elem[i];
            }
            usedSize--;
            modified = true;
            i = indexOf(data);
        }
        return modified;
    }

    public void update(int data, int index) {
        if (index < 0 || index >= usedSize) {
            throw new IndexOutOfBoundsException("下标出错");
        }
        elem[index] = data;
    }

    // 打印顺序表
    public void display() {
        for (int i = 0; i < usedSize; i++) {
            System.out.print(elem[i] + " ");
        }
        System.out.println();
    }

    // 获取顺序表长度
    public int size() {
        return usedSize;
    }

    // 清空顺序表
    public void clear() {
        usedSize = 0;
    }


}
